/**
 * 经典问题，只能向右或者向下走
 * 问从左上到右下的最小代价
 * 
 */
class Solution {

using vi = vector<int>;

vector<vi> D;
int N, M;

public:
    int minPathSum(vector<vector<int>>& grid) {
        N = grid.size();
        M = grid[0].size();
        D.assign(N + 1, vi(M + 1, -1));     

        D[1][1] = grid[0][0];
        for(int i=1;i<=N;++i)for(int j=1;j<=M;++j){
            if(1 == i and 1 == j) continue;
            auto v = grid[i - 1][j - 1];
            chkmin(D[i][j], D[i - 1][j]);
            chkmin(D[i][j], D[i][j - 1]);
            assert(D[i][j] != -1);
            D[i][j] += v;
        }
        return D[N][M];
    }

    void chkmin(int & d, int a){
        if(-1 == d or (-1 != a and a < d)) d = a;
    }
};